package offer.offer03;

import java.util.ArrayList;
import java.util.List;

/**
 * 插入的时候就直接用二分查找插入?
 */
public class Solution41 {
    List<Integer> list = new ArrayList<>();
    public Solution41() {

    }

    //我自己写个二分查找
    public void addNum(int num) {
        if(list.size() == 0){
            list.add(num);
            return;
        }
        if(num > list.get(list.size() - 1)){
            list.add(num);
            return;
        }else if(num < list.get(0)){
            list.add(0, num);
            return;
        }

        biInsert(num, 0, list.size());
    }

    public void biInsert(int num, int start, int end){
        if(end - start == 1){
            list.add(end, num);
            return;
        }
        if(num > list.get((end + start)/2)){
            biInsert(num, (end + start)/2, end);
        }else {
            biInsert(num, start, (end + start)/2);
        }
    }

    public double findMedian() {
        int size = list.size();
        if(size % 2 == 1){
            return list.get(size/2);
        }else {
            return ((double)list.get(size/2 - 1) + list.get(size/2))/2;
        }
    }

    public static void main(String[] args) {
        Solution41 s = new Solution41();
        s.addNum(1);
        s.addNum(2);
        System.out.println(s.findMedian());
        s.addNum(3);
        System.out.println(s.findMedian());
    }
}
